#include <stdio.h>

void PrintArray(int *a, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序  时间复杂度：O(n^2)
void BubbleSort(int *a, int size)
{
    for (int i = 0; i < size - 1; i++) // 将n个数归位
    {
        int flag = 0;
        for (int j = 0; j < size - i - 1; j++) // 两两比较  size - i - 1:每比较一次，就有一个数归位
        {
            if (a[j] > a[j + 1])
            {
                flag = 1;
                Swap(&a[j], &a[j + 1]);
            }
        }
        if (flag == 0) // 数列已经有序
        {
            break; // 跳出循环
        }
    }
}

// 插入排序
void InsertSort(int *a, int size)
{
    for (int i = 1; i < size; i++)
    {
        int j = i; // 这个位置是即将要插入的数
        int temp = a[j];
        for (; j > 0; j--)
        {
            if (a[j - 1] > temp) // 前面的数比我大
            {
                a[j] = a[j - 1]; // 空出来
            }
            else // 前面的数不比我大
            {
                break;
            }
        }
        a[j] = temp;
    }
}

// 选择排序
void ChooseSort(int *a, int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < size; j++)
        {
            if (a[min] > a[j])
            {
                min = j;
            }
        }
        Swap(&a[min], &a[i]);
    }
}

// 双指针算法
void ChooseSort2(int *a, int size) // 一次找两个,把最小的往左边移，最大的往右边移动
{
    int left = 0;
    int right = size - 1;
    while (left < right)
    {
        int min = left;
        int max = right;
        for (int i = left; i <= right; i++)
        {
            if (a[i] < a[min])
            {
                min = i;
            }
            if (a[i] > a[max])
            {
                max = i;
            }
        }
        Swap(&a[left], &a[min]);
        if (max == left)
        {
            max = min;
        }
        Swap(&a[right], &a[max]); // 极值在两端会有问题 (所以要加前面的if)
        left++;
        right--;
    }
}

// 快速排序
// 双指针 递归 分治
void FastSort(int *a, int start, int end)
{
    // 终止条件
    if (start >= end)
    {
        return;
    }
    int left = start;
    int right = end;
    int temp = a[start];
    while (left < right)
    {
        // 从右边往左边找比基准值小的    
        while (a[right] > temp && left < right)
        {
            right--;
        }
        if (left < right)
        {
            a[left++] = a[right]; // 把比基准值小的数放到左边去
        }
        // 从左边往右边找比基准值大的
        while (a[left] < temp && left < right)
        {
            left++;
        }
        if (left < right)
        {
            a[right--] = a[left]; // 把比基准值大的放右边
        }
    }
    a[left] = temp; // temp到了中间
    FastSort(a, start, left - 1);
    FastSort(a, right + 1, end);
}

//返回找到数组元素的下标
//二分法
int BinarySearch(int *a,int size,int element)
{
    int left = 0;
    int right = size - 1;
    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        if(a[mid]==element)
        {
            return mid;
        }
        else if(a[mid] > element)
        {
            right = mid-1;
        }
        else if(a[mid]<element)
        {
            left = mid +1;
        }
    }
    return -1;
}

int main()
{
    int a[] = {3, 65, 1, 46, 24, 100, 45, 2};
    //PrintArray(a, sizeof(a)/sizeof(a[0]));

    // BubbleSort(a, 5);
    // InsertSort(a, 5);
    FastSort(a, 0, sizeof(a)/sizeof(a[0]) - 1);
    // ChooseSort2(a, 8);

    int index = BinarySearch(a,sizeof(a)/sizeof(a[0]),100);
    if(index == -1)
    {
        printf("没找到\n");
    }
    else
    {
        printf("%d\n",index);
    }
    //PrintArray(a, 8);

    return 0;
}
